// 96. 不同的二叉搜索树
// https://leetcode.cn/problems/unique-binary-search-trees/

/**
输入：n = 3
输出：5

示例 2：

输入：n = 1
输出：1
 */

/**
 * @param {number} n
 * @return {number}
 */
var numTrees = function (n) {
    // 定义dp数组
    // dp[i] 为 1~i的所有搜索二叉树组合数量

    // 初始化dp
    // dp[0] 为1个空元素
    // dp[1] 就1个元素
    // dp[2] 1~2 [1,2] [2,1]
    let dp = [1, 1, 2];

    for (let i = 3; i <= n; i++) {
        let acc = 0;
        // 把j作为根节点，循环从1到i每个数作为根时，左右的组合
        for (let j = 1; j <= i; j++) {
            let left = dp[j - 1];
            let right = dp[i - j];

            acc += left * right;
        }
        dp.push(acc);
    }

    console.log(dp[n]);
    return dp[n];
};

numTrees(3); // [[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]
numTrees(1); // [[1]]
